class Solution{
public:
  int rob(TreeNode *root){

    vector<int> ans = robInternal(root);

    return max(ans.at(0), ans.at(1));

  }

  vector<int> robInternal(TreeNode *root){

    // 每个节点有两种状态：偷和不偷
    // res[0]表示不偷这个节点所能达到的最大值
    // res[1]表示偷这个节点所能达到的最大值
    vector<int> res(2, 0);
    if(root){
      vector<int> left = robInternal(root->left);
      vector<int> right = robInternal(root->right);

      // 不偷这个节点
      res.at(0) = max(left.at(0), left.at(1)) + max(right.at(0), right.at(1));
      // 偷这个节点
      res.at(1) = left.at(0) + right.at(0) + root->val;
    }

    return res;

  }
};